// https://leetcode.cn/problems/wiggle-subsequence/description/

// 算法思路总结：
// 1. 使用双状态动态规划求解最长摆动子序列
// 2. f[i]表示以i结尾且最后上升的最长长度
// 3. g[i]表示以i结尾且最后下降的最长长度
// 4. 时间复杂度：O(n²)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return 1; 

        int ret = 1;
        vector<int> f(m, 1), g(m, 1);
        for (int i = 1 ; i < m ; i++)
        {
            for (int j = 0 ; j < i ; j++)
            {
                if (nums[j] < nums[i])
                    f[i] = max(f[i], g[j] + 1);
                if (nums[j] > nums[i])
                    g[i] = max(g[i], f[j] + 1);
                ret = max({ret, f[i], g[i]});
            }
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {1,7,4,9,2,5}, v2 = {1,17,5,10,13,15,10,5,16,8};
    Solution sol;

    cout << sol.wiggleMaxLength(v1) << endl;
    cout << sol.wiggleMaxLength(v2) << endl;

    return 0;
}